/*
 * Copyright 2008 Neil Bacon
 * Distributed under the terms of the Mozilla Public License version 1.1
 * or the GNU General Public License version 3.
 */

package nb.xadd.operator.impl;

import nb.cache.CacheMap;
import nb.xadd.NotYetImplemented;
import nb.xadd.XADDRuntimeException;
import nb.xadd.node.Node;
import nb.xadd.node.NodeFactory;
import nb.xadd.node.impl.BooleanDecisionNode;
import nb.xadd.node.impl.ConstantValueNode;
import nb.xadd.node.impl.LinearValueNode;
import nb.xadd.node.impl.PolynomialValueNode;
import nb.xadd.node.impl.RealEqualDecisionNode;
import nb.xadd.node.impl.RealGreaterOrEqualDecisionNode;
import nb.xadd.operator.BinaryOperator;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * Handles recursive application of an BinaryOperator down the tree to the terminal nodes.
 * Subclasses only need to handle the terminal nodes.
 * 
 * {@link OperatorFactoryImpl} ensures that some BinaryOperators are Singletons (only one object of
 * each class), so the equals() and hashCode() inherited from Object are adequate for these.
 * Non Singleton operators will require a proper equals() and hashCode().
 * 
 */
public abstract class AbstractBinaryOperator implements BinaryOperator {

    private Log log = LogFactory.getLog(getClass());
    private final NodeFactory nodeFactory;
    private final CacheMap<ApplyCacheKey, Node> applyCache;

    protected AbstractBinaryOperator(NodeFactory nodeFactory, CacheMap<ApplyCacheKey, Node> applyCache) {
        this.nodeFactory = nodeFactory;
        this.applyCache = applyCache;
    }

    /**
     * Is BinaryOperator a no-op (does nothing) for this value?
     * @return true if no-op
     */
    protected abstract boolean isNoOp(ConstantValueNode c);

    protected NodeFactory getNodeFactory() {
        return nodeFactory;
    }

    /**
     * Bind value to variable.
     * @param n
     * @param realVarIndex specifies variable set to value
     * @param value
     * @return n evaluated with variable set to value.
     */
    private Node bind(Node n, int realVarIndex, double value) {
        Node result;
        if (n instanceof RealGreaterOrEqualDecisionNode) {
            RealGreaterOrEqualDecisionNode dn = (RealGreaterOrEqualDecisionNode) n;
            Node trueChild = bind(dn.getTrueChild(), realVarIndex, value);
            Node falseChild = bind(dn.getFalseChild(), realVarIndex, value);
            result = nodeFactory.getRealGreaterOrEqualDecisionNode(dn.getRealVarIndex(), dn.getTestValue(), trueChild, falseChild);
        } else if (n instanceof RealEqualDecisionNode) {
            RealEqualDecisionNode dn = (RealEqualDecisionNode) n;
            Node trueChild = bind(dn.getTrueChild(), realVarIndex, value);
            Node falseChild = bind(dn.getFalseChild(), realVarIndex, value);
            result = nodeFactory.getRealEqualDecisionNode(dn.getRealVarIndex(), dn.getTestValue(), trueChild, falseChild);
        } else if (n instanceof BooleanDecisionNode) {
            BooleanDecisionNode dn = (BooleanDecisionNode) n;
            Node trueChild = bind(dn.getTrueChild(), realVarIndex, value);
            Node falseChild = bind(dn.getFalseChild(), realVarIndex, value);
            result = nodeFactory.getBooleanDecisionNode(dn.getBooleanVarIndex(), trueChild, falseChild);
        } else if (n instanceof LinearValueNode) {
            result = bindLinear((LinearValueNode) n, realVarIndex, value);
        } else if (n instanceof PolynomialValueNode) {
            result = bindPolynomial((PolynomialValueNode) n, realVarIndex, value);
        } else {
            // ConstantValueNode
            result = n;
        }
//        if (log.isDebugEnabled()) {
//            log.debug("walk: result = " + result);
//        }
        return result;
    }
    
    /**
     * Bind value to variable.
     * TODO: Maybe move to NodeFactory.
     * @param n
     * @param realVarIndex specifies variable set to value
     * @param value
     * @return n evaluated with variable set to value.
     * Result is a LinearValueNode with coeff for realVarIndex set to zero,
     * or if that would result in no non-zero coeff, a ConstantValueNode.
     */
    private Node bindLinear(LinearValueNode n, int realVarIndex, double value) {
        if (log.isDebugEnabled()) {
            log.debug("bindLinear: Set x" + realVarIndex + " = " + value + " in n =\n" + n);
        }
        double[] coeff = n.getCoeff();
        // LinearValueNode has non-zero coeff for realVarIndex?
        if (realVarIndex < coeff.length && coeff[realVarIndex] != 0.0) {
            double constValue = n.getConstValue() + coeff[realVarIndex] * value;
            // any other non-zero coeffs?
            for (int i = 0; i < coeff.length; i++) {
                if (i != realVarIndex && coeff[i] != 0.0) {
                    // yes - return new LinearValueNode
                    coeff = n.getCopyOfCoeff();
                    coeff[realVarIndex] = 0.0;
                    return getNodeFactory().getLinearValueNode(constValue, coeff);
                }
            }
            // no - return ConstantValueNode
            return getNodeFactory().getConstantValueNode(constValue);
        } else {
            return n;
        }
    }

    /**
     * Bind value to variable.
     * Not yet implemented, just returns n.
     * @see #bindLinear(LinearValueNode, int, double)
     * TODO: Implement! Maybe move to NodeFactory.
     * @param n
     * @param realVarIndex specifies variable set to value
     * @param value
     * @return n evaluated with variable set to value.
     */
    private Node bindPolynomial(PolynomialValueNode n, int realVarIndex, double value) {
        throw new NotYetImplemented();
    }

    @Override
    public Node executeConstantBooleanDecision(ConstantValueNode n1, BooleanDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeConstantBooleanDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        if (isNoOp(n1)) {
            return n2;
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            Node trueChild = n2.getTrueChild().apply(this, n1);
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getBooleanDecisionNode(n2.getBooleanVarIndex(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executeConstantRealEqualDecision(ConstantValueNode n1, RealEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeConstantRealEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        if (isNoOp(n1)) {
            return n2;
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            Node trueChild = n2.getTrueChild().apply(this, n1);
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getRealEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executeConstantRealGreaterOrEqualDecision(ConstantValueNode n1, RealGreaterOrEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeConstantRealGreaterOrEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        if (isNoOp(n1)) {
            return n2;
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            Node trueChild = n2.getTrueChild().apply(this, n1);
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getRealGreaterOrEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executeLinearBooleanDecision(LinearValueNode n1, BooleanDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeLinearBooleanDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            Node trueChild = n2.getTrueChild().apply(this, n1);
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getBooleanDecisionNode(n2.getBooleanVarIndex(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executeLinearRealEqualDecision(LinearValueNode n1, RealEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeLinearRealEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            Node trueChild = n2.getTrueChild().apply(this, bindLinear(n1, n2.getRealVarIndex(), n2.getTestValue()));
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getRealEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executeLinearRealGreaterOrEqualDecision(LinearValueNode n1, RealGreaterOrEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeLinearRealGreaterOrEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            Node trueChild = n2.getTrueChild().apply(this, n1);
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getRealGreaterOrEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executePolynomialBooleanDecision(PolynomialValueNode n1, BooleanDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executePolynomialBooleanDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            Node trueChild = n2.getTrueChild().apply(this, n1);
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getBooleanDecisionNode(n2.getBooleanVarIndex(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executePolynomialRealEqualDecision(PolynomialValueNode n1, RealEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executePolynomialRealEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            // Node trueChild = n2.getTrueChild().apply(this, n1);
            Node trueChild = n2.getTrueChild().apply(this, bindPolynomial(n1, n2.getRealVarIndex(), n2.getTestValue()));
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getRealEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executePolynomialRealGreaterOrEqualDecision(PolynomialValueNode n1, RealGreaterOrEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executePolynomialRealGreaterOrEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            Node trueChild = n2.getTrueChild().apply(this, n1);
            Node falseChild = n2.getFalseChild().apply(this, n1);
            result = getNodeFactory().getRealGreaterOrEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executeBooleanDecisionBooleanDecision(BooleanDecisionNode n1, BooleanDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeBooleanDecisionBooleanDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            // if n1 comes before n2, split on n1, else split on n2
            if (n1.compareTo(n2) < 0) {
                log.debug("split on b" + n1.getBooleanVarIndex());
                Node trueChild = n1.getTrueChild().applyBooleanDecision(this, n2);
                Node falseChild = n1.getFalseChild().applyBooleanDecision(this, n2);
                result = getNodeFactory().getBooleanDecisionNode(n1.getBooleanVarIndex(), trueChild, falseChild);
            } else {
                log.debug("split on b" + n1.getBooleanVarIndex());
                Node trueChild = n2.getTrueChild().applyBooleanDecision(this, n1);
                Node falseChild = n2.getFalseChild().applyBooleanDecision(this, n1);
                result = getNodeFactory().getBooleanDecisionNode(n2.getBooleanVarIndex(), trueChild, falseChild);
            }
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executeBooleanDecisionRealEqualDecision(BooleanDecisionNode n1, RealEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeBooleanDecisionRealEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            // if n1 comes before n2, split on n1, else split on n2
            // later never happens because our ordering function always puts BooleanDecisions first
            if (n1.compareTo(n2) < 0) {
                Node trueChild = n1.getTrueChild().applyRealEqualDecision(this, n2);
                Node falseChild = n1.getFalseChild().applyRealEqualDecision(this, n2);
                result = getNodeFactory().getBooleanDecisionNode(n1.getBooleanVarIndex(), trueChild, falseChild);
            } else {
                Node trueChild = n2.getTrueChild().applyBooleanDecision(this, n1);
                Node falseChild = n2.getFalseChild().applyBooleanDecision(this, n1);
                result = getNodeFactory().getRealEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            }
            applyCache.put(key, result);
        }
        return result;
    }

    @Override
    public Node executeBooleanDecisionRealGreaterOrEqualDecision(BooleanDecisionNode n1, RealGreaterOrEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeBooleanDecisionRealGreaterOrEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            // if n1 comes before n2, split on n1, else split on n2
            // later never happens because our ordering function always puts BooleanDecisions first
            if (n1.compareTo(n2) < 0) {
                Node trueChild = n1.getTrueChild().applyRealGreaterOrEqualDecision(this, n2);
                Node falseChild = n1.getFalseChild().applyRealGreaterOrEqualDecision(this, n2);
                result = getNodeFactory().getBooleanDecisionNode(n1.getBooleanVarIndex(), trueChild, falseChild);
            } else {
                Node trueChild = n2.getTrueChild().applyBooleanDecision(this, n1);
                Node falseChild = n2.getFalseChild().applyBooleanDecision(this, n1);
                result = getNodeFactory().getRealGreaterOrEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            }
            applyCache.put(key, result);
        }
        return result;
    }

    public Node executeRealEqualDecisionRealEqualDecision(RealEqualDecisionNode n1, RealEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeRealEqualDecisionRealEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            // if n1 comes before n2, split on n1, else split on n2
            if (n1.compareTo(n2) < 0) {
                Node trueChild = n1.getTrueChild().applyRealEqualDecision(this, n2);
                Node falseChild = n1.getFalseChild().applyRealEqualDecision(this, n2);
                result = getNodeFactory().getRealEqualDecisionNode(n1.getRealVarIndex(), n1.getTestValue(), trueChild, falseChild);
            } else {
                Node trueChild = n2.getTrueChild().applyRealEqualDecision(this, n1);
                Node falseChild = n2.getFalseChild().applyRealEqualDecision(this, n1);
                result = getNodeFactory().getRealEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            }
            applyCache.put(key, result);
        }
        return result;
    }

    public Node executeRealEqualDecisionRealGreaterOrEqualDecision(RealEqualDecisionNode n1, RealGreaterOrEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeRealEqualDecisionRealGreaterOrEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            // if n1 comes before n2, split on n1, else split on n2
            // later never happens because ordering always puts RealEqualDecisions first
            if (n1.compareTo(n2) < 0) {
                Node trueChild;
                if (n1.getRealVarIndex() == n2.getRealVarIndex()) {
                    // eliminate redundant RealGreaterOrEqualDecision
                    Node n2Child = n1.getTestValue() >= n2.getTestValue() ? n2.getTrueChild() : n2.getFalseChild();
                    trueChild = n2Child.applyRealEqualDecision(this, n1);
                } else {
                    // TODO: we are recursive and bind() is too
                    // could restructure into a single more efficient recursion
                    trueChild = n1.getTrueChild().apply(this, bind(n2, n1.getRealVarIndex(), n1.getTestValue()));
                }
                Node falseChild = n1.getFalseChild().applyRealGreaterOrEqualDecision(this, n2);
                result = getNodeFactory().getRealEqualDecisionNode(n1.getRealVarIndex(), n1.getTestValue(), trueChild, falseChild);
            } else {
                throw new XADDRuntimeException("Incorrect node ordering.");
//                    Node trueChild = n2.getTrueChild().applyRealEqualDecision(this, n1);
//                    Node falseChild = n2.getFalseChild().applyRealEqualDecision(this, n1);
//                    result = getNodeFactory().getRealGreaterOrEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            }
            applyCache.put(key, result);
        }
        return result;
    }

    public Node executeRealGreaterOrEqualDecisionRealGreaterOrEqualDecision(RealGreaterOrEqualDecisionNode n1, RealGreaterOrEqualDecisionNode n2) {
        if (log.isDebugEnabled()) {
            log.debug("executeRealGreaterOrEqualDecisionRealGreaterOrEqualDecision: n1: " + n1.description() + ", n2: " + n2.description());
        }
        ApplyCacheKey key = new ApplyCacheKey(this, n1, n2);
        Node result = applyCache.get(key);
        if (result == null) {
            // if n1 comes before n2, split on n1, else split on n2
            if (n1.compareTo(n2) < 0) {
                Node trueChild = n1.getTrueChild().applyRealGreaterOrEqualDecision(this, n2);
                Node falseChild = n1.getFalseChild().applyRealGreaterOrEqualDecision(this, n2);
                result = getNodeFactory().getRealGreaterOrEqualDecisionNode(n1.getRealVarIndex(), n1.getTestValue(), trueChild, falseChild);
            } else {
                Node trueChild = n2.getTrueChild().applyRealGreaterOrEqualDecision(this, n1);
                Node falseChild = n2.getFalseChild().applyRealGreaterOrEqualDecision(this, n1);
                result = getNodeFactory().getRealGreaterOrEqualDecisionNode(n2.getRealVarIndex(), n2.getTestValue(), trueChild, falseChild);
            }
            applyCache.put(key, result);
        }
        return result;
    }

}
